<!DOCTYPE html>
<canvas class="fireworks" style="position: fixed;left: 0;top: 0;z-index: 1; pointer-events: none;"></canvas> 
<script type="text/javascript" src="//cdn.bootcss.com/animejs/2.2.0/anime.min.js"></script> 
<script type="text/javascript" src="/js/fireworks.js"></script>

<html lang="en">
<head><meta name="generator" content="Hexo 3.8.0">
    <meta charset="utf-8">
<title>PAT 小结 - Notouch</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">



    <meta name="description" content="🤹‍ 小技巧🚵 两个指针🤸‍ 递归时传递多个参数  typedef pair&amp;lt;int, int&amp;gt; P;">
<meta name="keywords" content="树状数组,LCS,算法,动态规划,堆排序,迪杰斯特拉算法，最短路径,拓扑排序,红黑树,hashing,背包问题,C++,二叉平衡树,完全二叉树">
<meta property="og:type" content="article">
<meta property="og:title" content="PAT 小结">
<meta property="og:url" content="http://notouch.top/2019/12/08/PAT-小结/index.html">
<meta property="og:site_name" content="Notouch">
<meta property="og:description" content="🤹‍ 小技巧🚵 两个指针🤸‍ 递归时传递多个参数  typedef pair&amp;lt;int, int&amp;gt; P;">
<meta property="og:locale" content="en">
<meta property="og:image" content="https://images.pexels.com/photos/3290601/pexels-photo-3290601.jpeg?auto=compress&cs=tinysrgb&dpr=1&w=500">
<meta property="og:updated_time" content="2019-12-08T10:57:54.213Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="PAT 小结">
<meta name="twitter:description" content="🤹‍ 小技巧🚵 两个指针🤸‍ 递归时传递多个参数  typedef pair&amp;lt;int, int&amp;gt; P;">
<meta name="twitter:image" content="https://images.pexels.com/photos/3290601/pexels-photo-3290601.jpeg?auto=compress&cs=tinysrgb&dpr=1&w=500">







<link rel="icon" href="/images/bitbug_favicon.ico">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/monokai-sublime.css">


    
    
    
    <style>body>.footer,body>.navbar,body>.section{opacity:0}</style>
    

    
    
    
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">
    

    
    

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">


    
    
    
    

<link rel="stylesheet" href="/css/back-to-top.css">


    
    

    
    
    
    

    
    
<link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

    
    
    

    
    
    
        <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    

    


<link rel="stylesheet" href="/css/style.css">
</head>

<script src="https://cdn.zrahh.com/js/instantclick-1.2.2.js" type="module"></script>

<body class="is-3-column">
	<!-- 样式二（飘动的彩带） -->
	<script src="https://g.joyinshare.com/hc/piao.js" type="text/javascript"></script>
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/dk_logo.svg" alt="PAT 小结" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item" href="/">Home</a>
                
                <a class="navbar-item" href="/archives">Archives</a>
                
                <a class="navbar-item" href="/categories">Categories</a>
                
                <a class="navbar-item" href="/tags">Tags</a>
                
                <a class="navbar-item" href="/about">About</a>
                
            </div>
            
            <div class="navbar-end">
                
                    
                    
                    <a class="navbar-item" target="_blank" title="Download on GitHub" href="https://github.com/duankong">
                        
                        <i class="fab fa-github"></i>
                        
                    </a>
                    
                
                
                <a class="navbar-item is-hidden-tablet catalogue" title="Catalogue" href="javascript:;">
                    <i class="fas fa-list-ul"></i>
                </a>
                
                
                <a class="navbar-item search" title="Search" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>
    
    
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-6-tablet is-6-desktop is-9-widescreen has-order-2 column-main"><div class="card">
	

    
    <div class="card-image">
        <span class="image is-7by1">
            <img class="thumbnail" src="https://images.pexels.com/photos/3290601/pexels-photo-3290601.jpeg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="PAT 小结">
        </span>
    </div>
    
    
    <div class="card-content article ">
		
        
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
            
			
                <time class="level-item has-text-grey" datetime="2019-12-08T10:09:29.000Z">2019-12-08</time>
                
                
                <div class="level-item">
                <a class="has-link-grey -link" href="/categories/C/">C++</a>&nbsp;/&nbsp;<a class="has-link-grey -link" href="/categories/C/PAT-Note/">PAT Note</a>
                </div>
                
                
                <span class="level-item has-text-grey">
                    
                    
                    15 minutes read (About 2189 words)
                </span>
                
                
                <span class="level-item has-text-grey" id="busuanzi_container_page_pv">
                    <i class="far fa-eye"></i>
                    <span id="busuanzi_value_page_pv">0</span> visits
                </span>
                
            </div>
        </div>
        
        
		
		
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
			
            
                PAT 小结
            

        </h1>
        
        <div class="content">
            <h2 id="🤹‍-小技巧"><a href="#🤹‍-小技巧" class="headerlink" title="🤹‍ 小技巧"></a>🤹‍ 小技巧</h2><h4 id="🚵-两个指针"><a href="#🚵-两个指针" class="headerlink" title="🚵 两个指针"></a>🚵 两个指针</h4><h4 id="🤸‍-递归时传递多个参数-typedef-pair-lt-int-int-gt-P"><a href="#🤸‍-递归时传递多个参数-typedef-pair-lt-int-int-gt-P" class="headerlink" title="🤸‍ 递归时传递多个参数  typedef pair&lt;int, int&gt; P;"></a>🤸‍ 递归时传递多个参数  typedef pair&lt;int, int&gt; P;</h4><a id="more"></a> 

<h2 id="🏊‍-算法"><a href="#🏊‍-算法" class="headerlink" title="🏊‍ 算法"></a>🏊‍ 算法</h2><h2 id="🥘-二叉平衡树（Balanced-Binary-Tree）"><a href="#🥘-二叉平衡树（Balanced-Binary-Tree）" class="headerlink" title="🥘 二叉平衡树（Balanced Binary Tree）"></a>🥘 二叉平衡树（Balanced Binary Tree）</h2><h4 id="🍦-定义"><a href="#🍦-定义" class="headerlink" title="🍦 定义"></a>🍦 定义</h4><p>平衡二叉树，基于avl算法，即是avl树（avl tree）</p>
<p>特点：</p>
<ol>
<li>符合二叉树的条件下</li>
<li>任何节点的两个子树的高度最大差为1</li>
<li>如果在avl 树，中进行插入和删除节点操作，可能导致avl树失去平衡，那么可以通过旋转重新达到平衡。因此我们说的二叉树也称自平衡二叉树。</li>
</ol>
<h4 id="🍯-C-实现建立树"><a href="#🍯-C-实现建立树" class="headerlink" title="🍯 C++实现建立树"></a>🍯 C++实现建立树</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="hljs-class"><span class="hljs-keyword">struct</span> <span class="hljs-title">node</span> //节点</span></span><br><span class="line"><span class="hljs-class">&#123;</span></span><br><span class="line">	<span class="hljs-keyword">int</span> data;</span><br><span class="line">	node *left = <span class="hljs-literal">NULL</span>;</span><br><span class="line">	node*right = <span class="hljs-literal">NULL</span>;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getheight</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//高度</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root == <span class="hljs-literal">NULL</span>)</span><br><span class="line">		<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;</span><br><span class="line">	<span class="hljs-keyword">return</span> max(getheight(root-&gt;left), getheight(root-&gt;right)) + <span class="hljs-number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function">node * <span class="hljs-title">right_exchange</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//右旋</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	node *t = root-&gt;left;</span><br><span class="line">	root-&gt;left = t-&gt;right;</span><br><span class="line">	t-&gt;right = root;</span><br><span class="line">	<span class="hljs-keyword">return</span> t;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function">node * <span class="hljs-title">left_exchange</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//左旋</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	node *t = root-&gt;right;</span><br><span class="line">	root-&gt;right = t-&gt;left;</span><br><span class="line">	t-&gt;left = root;</span><br><span class="line">	<span class="hljs-keyword">return</span> t;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function">node * <span class="hljs-title">lr_exchange</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//左右旋</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	root-&gt;left = left_exchange(root-&gt;left);</span><br><span class="line">	<span class="hljs-keyword">return</span> right_exchange(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function">node * <span class="hljs-title">rl_exchange</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//右左旋</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	root-&gt;right = right_exchange(root-&gt;right);</span><br><span class="line">	<span class="hljs-keyword">return</span> left_exchange(root);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function">node *<span class="hljs-title">build_AVL</span><span class="hljs-params">(node *root, <span class="hljs-keyword">int</span> data)</span><span class="hljs-comment">//建立</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root == <span class="hljs-literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		root = <span class="hljs-keyword">new</span> node;</span><br><span class="line">		root-&gt;data = data;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (data &lt; root-&gt;data)</span><br><span class="line">		&#123;</span><br><span class="line">			root-&gt;left = build_AVL(root-&gt;left, data);</span><br><span class="line">			<span class="hljs-keyword">if</span> (getheight(root-&gt;left) - getheight(root-&gt;right) == <span class="hljs-number">2</span>)</span><br><span class="line">				root=data &lt; root-&gt;left-&gt;data ? right_exchange(root) : lr_exchange(root);</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="hljs-keyword">else</span></span><br><span class="line">		&#123;</span><br><span class="line">			root-&gt;right = build_AVL(root-&gt;right, data);</span><br><span class="line">			<span class="hljs-keyword">if</span> (getheight(root-&gt;right) - getheight(root-&gt;left) == <span class="hljs-number">2</span>)</span><br><span class="line">				root=data &gt; root-&gt;right-&gt;data ? left_exchange(root) : rl_exchange(root);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">return</span> root;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="🍵-完全二叉树（complete-binary-tree）"><a href="#🍵-完全二叉树（complete-binary-tree）" class="headerlink" title="🍵 完全二叉树（complete binary tree）"></a>🍵 完全二叉树（complete binary tree）</h2><h4 id="🥂-定义"><a href="#🥂-定义" class="headerlink" title="🥂 定义"></a>🥂 定义</h4><p>&emsp;&emsp;若设二叉树的深度为h，除第 h 层外，其它各层 (1–h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。<br>&emsp;&emsp;完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。</p>
<ul>
<li>(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）</li>
<li>(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。</li>
</ul>
<p>&emsp;&emsp;一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。</p>
<h4 id="🏺-判断（C-实现）"><a href="#🏺-判断（C-实现）" class="headerlink" title="🏺 判断（C++实现）"></a>🏺 判断（C++实现）</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">int</span> maxn = <span class="hljs-number">-1</span>;</span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">dfs</span><span class="hljs-params">(node * root, <span class="hljs-keyword">int</span> num)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root-&gt;left == <span class="hljs-literal">NULL</span> &amp;&amp; root-&gt;right == <span class="hljs-literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (num &gt; maxn)</span><br><span class="line">		&#123;</span><br><span class="line">			maxn = num;</span><br><span class="line">			<span class="hljs-keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root-&gt;left != <span class="hljs-literal">NULL</span>)</span><br><span class="line">		dfs(root-&gt;left, <span class="hljs-number">2</span> * num);</span><br><span class="line">	<span class="hljs-keyword">if</span> (root-&gt;right != <span class="hljs-literal">NULL</span>)</span><br><span class="line">		dfs(root-&gt;right, <span class="hljs-number">2</span> * num + <span class="hljs-number">1</span>);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-built_in">cin</span> &gt;&gt; n;</span><br><span class="line">	node *root = <span class="hljs-literal">NULL</span>;</span><br><span class="line">	<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-built_in">cin</span> &gt;&gt; k;</span><br><span class="line">		root = build_AVL(root, k);</span><br><span class="line">	&#125;</span><br><span class="line">	bfs(root);</span><br><span class="line">	show_res(res);</span><br><span class="line">	dfs(root, <span class="hljs-number">1</span>);</span><br><span class="line">	<span class="hljs-keyword">if</span> (maxn == n)</span><br><span class="line">		<span class="hljs-built_in">printf</span>(<span class="hljs-string">"YES\n"</span>);</span><br><span class="line">	<span class="hljs-keyword">else</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-built_in">printf</span>(<span class="hljs-string">"NO\n"</span>);</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="🏄-LCS-最长公共子序列"><a href="#🏄-LCS-最长公共子序列" class="headerlink" title="🏄 LCS 最长公共子序列"></a>🏄 LCS 最长公共子序列</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">while</span>(<span class="hljs-built_in">scanf</span>(<span class="hljs-string">"%s%s"</span>,a,b)!=EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="hljs-built_in">memset</span>(dp,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span>(dp));</span><br><span class="line">        lena=<span class="hljs-built_in">strlen</span>(a);</span><br><span class="line">        lenb=<span class="hljs-built_in">strlen</span>(b);</span><br><span class="line">        <span class="hljs-keyword">for</span>(i=<span class="hljs-number">1</span>;i&lt;=lena;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="hljs-keyword">for</span>(j=<span class="hljs-number">1</span>;j&lt;=lenb;j++)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="hljs-keyword">if</span>(a[i<span class="hljs-number">-1</span>]==b[j<span class="hljs-number">-1</span>])</span><br><span class="line">                &#123;</span><br><span class="line">                    dp[i][j]=dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]+<span class="hljs-number">1</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="hljs-keyword">else</span></span><br><span class="line">                &#123;</span><br><span class="line">                    dp[i][j]=max(dp[i<span class="hljs-number">-1</span>][j],dp[i][j<span class="hljs-number">-1</span>]);</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d\n"</span>,dp[lena][lenb]);</span><br><span class="line">    &#125;</span><br></pre></td></tr></table></figure>

<h4 id="🛀-堆排序-1098-Insertion-or-Heap-Sort-25"><a href="#🛀-堆排序-1098-Insertion-or-Heap-Sort-25" class="headerlink" title="🛀 堆排序 1098 Insertion or Heap Sort (25)"></a>🛀 堆排序 1098 Insertion or Heap Sort (25)</h4><ul>
<li>步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。</li>
</ul>
<ul>
<li>步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。</li>
</ul>
<h6 id="👭-实现"><a href="#👭-实现" class="headerlink" title="👭 实现"></a>👭 实现</h6><blockquote>
<p>堆排序的特点是后面是从小到大的，前面的顺序不一定，又因为是从小到大排列，堆排序之前堆为大顶堆，前面未排序的序列的最大值为b[1]，那么就可以从n开始往前找，</p>
</blockquote>
<p>1) 找第一个小于等于b[1]的数字b[p]（while(p &gt; 2 &amp;&amp; b[p] &gt;= b[1]) p–;)把它和第一个数字交换（swap(b[1],b[p]);)</p>
<p>2) 然后把数组b在1~p-1区间进行一次向下调整（downAdjust(b, 1,  p -1);)向下调整，low和high是需要调整的区间，因为是大顶堆，就是不断比较当前结点和自己的孩子结点哪个大，如果孩子大就把孩子结点和自己交换，然后再不断调整直到到达区间的最大值不能再继续了为止.</p>
<figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">downAdjust</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; &amp;b, <span class="hljs-keyword">int</span> low, <span class="hljs-keyword">int</span> high)</span></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>, j = <span class="hljs-number">2</span> * i+<span class="hljs-number">1</span>;</span><br><span class="line">	<span class="hljs-keyword">while</span> (j&lt;=high)&#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (j + <span class="hljs-number">1</span> &lt;= high &amp;&amp; b[j] &lt; b[j+<span class="hljs-number">1</span>]) j = j + <span class="hljs-number">1</span>;</span><br><span class="line">		<span class="hljs-keyword">if</span> (b[i] &gt;= b[j])</span><br><span class="line">			<span class="hljs-keyword">break</span>;</span><br><span class="line">		swap(b[i], b[j]);</span><br><span class="line">		i = j; j = <span class="hljs-number">2</span> * i+<span class="hljs-number">1</span>;<span class="hljs-comment">//调整换了的部分是否乱序了</span></span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">main</span><span class="hljs-params">()</span></span>&#123;</span><br><span class="line">	<span class="hljs-built_in">cin</span> &gt;&gt; n;</span><br><span class="line">	a.resize(n);</span><br><span class="line">	b.resize(n);</span><br><span class="line">	<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)</span><br><span class="line">		<span class="hljs-built_in">cin</span> &gt;&gt; a[i];</span><br><span class="line">	<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; n; i++)</span><br><span class="line">		<span class="hljs-built_in">cin</span> &gt;&gt; b[i];</span><br><span class="line">	<span class="hljs-comment">//process</span></span><br><span class="line">	<span class="hljs-keyword">int</span> i, j;</span><br><span class="line">	<span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i &lt; n&amp;&amp;b[i] &lt;= b[i + <span class="hljs-number">1</span>]; i++);</span><br><span class="line">	<span class="hljs-keyword">for</span> (j = i + <span class="hljs-number">1</span>; j &lt; n&amp;&amp;a[j] == b[j]; j++);</span><br><span class="line">	<span class="hljs-keyword">if</span> (j == n)&#123;</span><br><span class="line">		<span class="hljs-built_in">printf</span>(<span class="hljs-string">"Insertion Sort\n"</span>);</span><br><span class="line">		sort(a.begin(), a.begin() + i + <span class="hljs-number">2</span>);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">else</span>&#123;</span><br><span class="line">		<span class="hljs-built_in">printf</span>(<span class="hljs-string">"Heap Sort\n"</span>);</span><br><span class="line">		<span class="hljs-keyword">int</span> p = n<span class="hljs-number">-1</span>;</span><br><span class="line">		<span class="hljs-keyword">while</span> (p &gt; <span class="hljs-number">1</span> &amp;&amp; b[p] &gt;= b[<span class="hljs-number">0</span>])</span><br><span class="line">			p--;</span><br><span class="line">		<span class="hljs-comment">//printf("p is %d\n", p);</span></span><br><span class="line">		swap(b[<span class="hljs-number">0</span>], b[p]);</span><br><span class="line">		downAdjust(b, <span class="hljs-number">0</span>, p - <span class="hljs-number">1</span>);</span><br><span class="line">		a = b;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">for</span> (j = <span class="hljs-number">0</span>; j &lt; n; j++) &#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (j != <span class="hljs-number">0</span>) <span class="hljs-built_in">printf</span>(<span class="hljs-string">" "</span>);</span><br><span class="line">		<span class="hljs-built_in">printf</span>(<span class="hljs-string">"%d"</span>, a[j]);</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-built_in">printf</span>(<span class="hljs-string">"\n"</span>);</span><br><span class="line">	<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="💑-树状数组"><a href="#💑-树状数组" class="headerlink" title="💑 树状数组"></a>💑 树状数组</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">lowbit</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">    <span class="hljs-keyword">return</span> n&amp;(-n);</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">update</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n,<span class="hljs-keyword">int</span> num)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">    <span class="hljs-keyword">while</span>(n&lt;=MAX)</span><br><span class="line">    &#123;</span><br><span class="line">        TreeArray[n]+=num;</span><br><span class="line">        n+=lowbit(n);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">GetSum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span><span class="hljs-comment">//前n个元素的和</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">    <span class="hljs-keyword">int</span> sum=<span class="hljs-number">0</span>;</span><br><span class="line">    <span class="hljs-keyword">while</span>(n&gt;<span class="hljs-number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        sum+=TreeArray[n];</span><br><span class="line">        n-=lowbit(n);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="hljs-keyword">return</span> sum;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">BinarySearch</span><span class="hljs-params">(<span class="hljs-keyword">int</span> target)</span>  <span class="hljs-comment">//二分查找</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;                             </span><br><span class="line">                              </span><br><span class="line">    <span class="hljs-keyword">int</span> mid;</span><br><span class="line">	<span class="hljs-keyword">int</span> left = <span class="hljs-number">1</span>, right = MAX_NUM;</span><br><span class="line">	<span class="hljs-keyword">while</span> (left&lt;=right)</span><br><span class="line">	&#123;</span><br><span class="line">		mid = left + (right - left) / <span class="hljs-number">2</span>;</span><br><span class="line">		<span class="hljs-keyword">if</span> (getsum(mid)&lt;target)</span><br><span class="line">			left = mid + <span class="hljs-number">1</span>;</span><br><span class="line">		<span class="hljs-keyword">else</span></span><br><span class="line">			right = mid - <span class="hljs-number">1</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-built_in">cout</span> &lt;&lt; left &lt;&lt; <span class="hljs-built_in">endl</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="👩‍👩‍👧-单源最短路径-迪杰斯特拉算法"><a href="#👩‍👩‍👧-单源最短路径-迪杰斯特拉算法" class="headerlink" title="👩‍👩‍👧 单源最短路径 迪杰斯特拉算法"></a>👩‍👩‍👧 单源最短路径 迪杰斯特拉算法</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">Dijkstra</span><span class="hljs-params">(<span class="hljs-keyword">int</span> u)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-built_in">memset</span>(vis,<span class="hljs-number">0</span>,<span class="hljs-keyword">sizeof</span>(vis));</span><br><span class="line">	<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> t=<span class="hljs-number">1</span>;t&lt;=n;t++)</span><br><span class="line">	&#123;</span><br><span class="line">		dis[t]=<span class="hljs-built_in">map</span>[u][t];<span class="hljs-comment">//初始化</span></span><br><span class="line">	&#125;</span><br><span class="line">	vis[u]=<span class="hljs-number">1</span>;</span><br><span class="line">	<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> t=<span class="hljs-number">1</span>;t&lt;n;t++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-keyword">int</span> minn=Inf,temp;</span><br><span class="line">		<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="hljs-keyword">if</span>(!vis[i]&amp;&amp;dis[i]&lt;minn)</span><br><span class="line">			&#123;</span><br><span class="line">				minn=dis[i];</span><br><span class="line">				temp=i;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		vis[temp]=<span class="hljs-number">1</span>;</span><br><span class="line">		<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>;i&lt;=n;i++)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="hljs-keyword">if</span>(vis[i]==<span class="hljs-number">0</span>&amp;&amp;<span class="hljs-built_in">map</span>[temp][i]+dis[temp]&lt;dis[i])</span><br><span class="line">			&#123;</span><br><span class="line">				dis[i]=<span class="hljs-built_in">map</span>[temp][i]+dis[temp];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="👥-拓扑排序-1146-Topological-Order-25-分"><a href="#👥-拓扑排序-1146-Topological-Order-25-分" class="headerlink" title="👥 拓扑排序 1146 Topological Order (25 分)"></a>👥 拓扑排序 1146 Topological Order (25 分)</h4><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">jujle</span><span class="hljs-params">(<span class="hljs-built_in">vector</span>&lt;<span class="hljs-keyword">int</span>&gt; s)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	fill(vis, vis + <span class="hljs-number">1001</span>, <span class="hljs-number">0</span>);</span><br><span class="line">	<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; s.size(); i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (vis[s[i]] == <span class="hljs-number">1</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; node[s[i]].size(); j++)<span class="hljs-comment">//判断每个父节点全被遍历过</span></span><br><span class="line">		&#123;</span><br><span class="line">			<span class="hljs-keyword">if</span>(vis[node[s[i]][j]]==<span class="hljs-number">0</span>)</span><br><span class="line">				<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">		&#125;</span><br><span class="line"></span><br><span class="line">		vis[s[i]] = <span class="hljs-number">1</span>;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="🦄-红黑树-1135-Is-It-A-Red-Black-Tree-30-分"><a href="#🦄-红黑树-1135-Is-It-A-Red-Black-Tree-30-分" class="headerlink" title="🦄 红黑树 1135 Is It A Red-Black Tree (30 分)"></a>🦄 红黑树 1135 Is It A Red-Black Tree (30 分)</h4><h6 id="🦏-定义"><a href="#🦏-定义" class="headerlink" title="🦏 定义"></a>🦏 定义</h6><p>红黑树的特性:<br>（1）每个节点或者是黑色，或者是红色。<br>（2）根节点是黑色。<br>（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]<br>（4）如果一个节点是红色的，则它的子节点必须是黑色的。<br>（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。</p>
<h6 id="🕊-规则4C-判断"><a href="#🕊-规则4C-判断" class="headerlink" title="🕊 规则4C++判断"></a>🕊 规则4C++判断</h6><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">prop4</span><span class="hljs-params">(node *root)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root == <span class="hljs-literal">NULL</span>)</span><br><span class="line">		<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root-&gt;data &lt; <span class="hljs-number">0</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="hljs-keyword">if</span> (root-&gt;left != <span class="hljs-literal">NULL</span> &amp;&amp; root-&gt;left-&gt;data &lt; <span class="hljs-number">0</span>)</span><br><span class="line">			<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">		<span class="hljs-keyword">if</span> (root-&gt;right != <span class="hljs-literal">NULL</span> &amp;&amp; root-&gt;right-&gt;data &lt; <span class="hljs-number">0</span>)</span><br><span class="line">			<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">return</span> prop4(root-&gt;left) &amp;&amp; prop4(root-&gt;right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h6 id="🐠-规则5C-判断"><a href="#🐠-规则5C-判断" class="headerlink" title="🐠 规则5C++判断"></a>🐠 规则5C++判断</h6><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">getnum</span><span class="hljs-params">(node *root)</span><span class="hljs-comment">//得到经过的黑节点</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root == <span class="hljs-literal">NULL</span>)</span><br><span class="line">		<span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;</span><br><span class="line">	<span class="hljs-keyword">int</span> l = getnum(root-&gt;left);</span><br><span class="line">	<span class="hljs-keyword">int</span> r = getnum(root-&gt;right);</span><br><span class="line">	<span class="hljs-keyword">return</span> root-&gt;data &gt; <span class="hljs-number">0</span> ? max(l, r) + <span class="hljs-number">1</span> : max(l, r);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">prop5</span><span class="hljs-params">(node* root)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">if</span> (root == <span class="hljs-literal">NULL</span>)<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;</span><br><span class="line">	<span class="hljs-keyword">int</span> l = getnum(root-&gt;left);</span><br><span class="line">	<span class="hljs-keyword">int</span> r = getnum(root-&gt;right);</span><br><span class="line">	<span class="hljs-keyword">if</span> (l != r) <span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">	<span class="hljs-keyword">return</span> prop5(root-&gt;left) &amp;&amp; prop5(root-&gt;right);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="🦂-Hashing-插入和查找-1078-Hashing-25-分-1145-Hashing-Average-Search-Time-25-分"><a href="#🦂-Hashing-插入和查找-1078-Hashing-25-分-1145-Hashing-Average-Search-Time-25-分" class="headerlink" title="🦂 Hashing 插入和查找: 1078 Hashing (25 分) 1145 Hashing - Average Search Time (25 分)"></a>🦂 Hashing 插入和查找: 1078 Hashing (25 分) 1145 Hashing - Average Search Time (25 分)</h4><h6 id="🌺-插入"><a href="#🌺-插入" class="headerlink" title="🌺 插入"></a>🌺 插入</h6><blockquote>
<p>Quadratic probing (with positive increments only) is used to solve the collisions.</p>
</blockquote>
<figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt;= msize; j++)<span class="hljs-comment">//等于</span></span><br><span class="line">&#123;</span><br><span class="line">	position = (key%msize + j * j) % msize;<span class="hljs-comment">//主要</span></span><br><span class="line">	<span class="hljs-keyword">if</span> (vis[position] == <span class="hljs-number">0</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		vis[position] = <span class="hljs-number">1</span>;</span><br><span class="line">		find_ = <span class="hljs-literal">true</span>;</span><br><span class="line">		<span class="hljs-keyword">break</span>;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h6 id="🌻-查找"><a href="#🌻-查找" class="headerlink" title="🌻 查找"></a>🌻 查找</h6><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-function"><span class="hljs-keyword">bool</span> <span class="hljs-title">search</span><span class="hljs-params">(<span class="hljs-keyword">int</span> n)</span></span></span><br><span class="line"><span class="hljs-function"></span>&#123;</span><br><span class="line">	<span class="hljs-keyword">int</span> position = n % msize;</span><br><span class="line">	<span class="hljs-keyword">int</span> cnt = <span class="hljs-number">0</span>;</span><br><span class="line">	<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt;=msize; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		position = (n%msize + i * i) % msize;<span class="hljs-comment">//注意是等于n，和插入时一样</span></span><br><span class="line">		tot++;</span><br><span class="line">		<span class="hljs-keyword">if</span> (htable[position] == n)<span class="hljs-comment">//找到了</span></span><br><span class="line">			<span class="hljs-keyword">return</span> <span class="hljs-literal">true</span>;</span><br><span class="line">		<span class="hljs-keyword">if</span> (htable[position] == <span class="hljs-number">0</span>)<span class="hljs-comment">//没有这个数</span></span><br><span class="line">			<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="hljs-keyword">return</span> <span class="hljs-literal">false</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="🍂-背包问题"><a href="#🍂-背包问题" class="headerlink" title="🍂 背包问题"></a>🍂 背包问题</h4><p> 有n件物品，每件物品的重量为w[i]，价值为c[i]。现有一个重量为V的背包，问如何选取物品放入背包，使得背包内物品的总价值最大。其中每种物品只有1件</p>
<pre><code>dp[i][j]表示前i件物品恰好装入容量为j的背包所能获得的最大价值
1、不放第i件物品，则 dp[i][j] = dp[i-1][j]
2、放第i件物品，那么问题转化为前i – 1件物品恰好装入容量j – w[i]的背包中所能获得的最大价值 dp[i-1][j-w[i]] + c[i]
3、递推方程dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);</code></pre><h6 id="🍇-通用解法"><a href="#🍇-通用解法" class="headerlink" title="🍇 通用解法"></a>🍇 通用解法</h6><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= n; i++) </span><br><span class="line">&#123;</span><br><span class="line">    <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = m; j &gt;= w[i]; j--)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="hljs-keyword">if</span>(dp[j] &lt;= dp[j-w[i]] + w[i]) </span><br><span class="line">        &#123;<span class="hljs-comment">//当容量为j时，放进去可以得到更高价值</span></span><br><span class="line">            choice[i][j] = <span class="hljs-literal">true</span>;<span class="hljs-comment">//flag</span></span><br><span class="line">            dp[j] = dp[j-w[i]] + w[i];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h6 id="🍑-一维"><a href="#🍑-一维" class="headerlink" title="🍑 一维"></a>🍑 一维</h6><figure class="highlight c++ hljs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= n; i++) &#123;</span><br><span class="line">  <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = v; j &gt;= w[i]; j--)</span><br><span class="line">    dp[v] = max(dp[v], dp[v-w[i]] + c[i]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<hr>
<p> 🌰 以上。(づ●─●)づ</p>
<p>转载请注明：<a href="http://notouch.top">Duankong的博客</a> » <a href="https://notouch.top/2019/12/08/PAT-小结/#more">点击阅读原文</a></p>

        </div>
        
        <div class="level is-size-7 is-uppercase">
            <div class="level-start">
                <div class="level-item">
                    <span class="is-size-6 has-text-grey has-mr-7">#</span>
                    <a class="has-link-grey -link" href="/tags/C/">C++</a>, <a class="has-link-grey -link" href="/tags/LCS/">LCS</a>, <a class="has-link-grey -link" href="/tags/hashing/">hashing</a>, <a class="has-link-grey -link" href="/tags/二叉平衡树/">二叉平衡树</a>, <a class="has-link-grey -link" href="/tags/动态规划/">动态规划</a>, <a class="has-link-grey -link" href="/tags/堆排序/">堆排序</a>, <a class="has-link-grey -link" href="/tags/完全二叉树/">完全二叉树</a>, <a class="has-link-grey -link" href="/tags/拓扑排序/">拓扑排序</a>, <a class="has-link-grey -link" href="/tags/树状数组/">树状数组</a>, <a class="has-link-grey -link" href="/tags/算法/">算法</a>, <a class="has-link-grey -link" href="/tags/红黑树/">红黑树</a>, <a class="has-link-grey -link" href="/tags/背包问题/">背包问题</a>, <a class="has-link-grey -link" href="/tags/迪杰斯特拉算法，最短路径/">迪杰斯特拉算法，最短路径</a>
                </div>
            </div>
        </div>
        
        
        
        
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js@1.0.16/dist/css/share.min.css">
<script src="https://cdn.jsdelivr.net/npm/social-share.js@1.0.16/dist/js/social-share.min.js"></script>

        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="menu-label has-text-centered">Like this article? Support the author with</h3>
        <div class="buttons is-centered">
            
                
<a class="button is-info donate">
    <span class="icon is-small">
        <i class="fab fa-alipay"></i>
    </span>
    <span>Alipay</span>
    <div class="qrcode"><img src="/images/o_timg.gif" alt="Alipay"></div>
</a>

                
                
<a class="button is-success donate">
    <span class="icon is-small">
        <i class="fab fa-weixin"></i>
    </span>
    <span>Wechat</span>
    <div class="qrcode"><img src="/images/xiaomai.gif" alt="Wechat"></div>
</a>

                
                
<a class="button is-danger donate" href="https://github.com/duankong" target="_blank">
    <span class="icon is-small">
        <i class="fab fa-patreon"></i>
    </span>
    <span>Patreon</span>
</a>

                
        </div>
    </div>
</div>




<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/2019/12/09/Function-for-Check/">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">Function for Check</span>
            </a>
        </div>
        
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/2019/12/08/PAT-Note-2/">
                <span class="level-item">PAT Note 2</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>



<div class="card">
    <div class="card-content">
        <h3 class="title is-5 has-text-weight-normal">Comments</h3>
        
<div id="comment-container"></div>
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/gitalk@1.4.1/dist/gitalk.css">
<script src="https://cdn.jsdelivr.net/npm/gitalk@1.4.1/dist/gitalk.min.js"></script>
<script>
    var gitalk = new Gitalk({
        clientID: '6cd559678e1f221043a2',
        clientSecret: '80e2f67e1a4202407fa9624190ed476d7cb3a86d',
        id: '8690ab849d6127c811cab309bb39dd1f',
        repo: 'duankong.github.io',
        owner: 'duankong',
        admin: "duankong"
    })
    gitalk.render('comment-container')
</script>

    </div>
</div>
</div>
                

<!-- 粘贴的部分 -->
                          <!-- 修改，可选保留的栏 -->




<div class="column is-4-tablet is-4-desktop is-3-widescreen  has-order-3 column-left is-sticky">
    
        
<div class="card widget">
    <div class="card-content">
        <nav class="level">
            <div class="level-item has-text-centered">
                <div>
                    
                        <img class="image is-128x128 has-mb-6" src="/images/xiaomai.gif" alt="Duankong">
                    
                    
                    <p class="is-size-4 is-block">
                        Duankong
                    </p>
                    
                    
                    <p class="is-size-6 is-block">
                        🌅总之岁月漫长，然而值得等待！
                    </p>
                    
                    
                    <p class="is-size-6 is-flex is-flex-center has-text-grey">
                        <i class="fas fa-map-marker-alt has-mr-7"></i>
                        <span>Wuhan.Hubei</span>
                    </p>
                    
                </div>
            </div>
        </nav>
        <nav class="level is-mobile">
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Posts
                    </p>
                    <p class="title has-text-weight-normal">
                        14
                    </p>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Categories
                    </p>
                    <p class="title has-text-weight-normal">
                        9
                    </p>
                </div>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <div>
                    <p class="heading">
                        Tags
                    </p>
                    <p class="title has-text-weight-normal">
                        50
                    </p>
                </div>
            </div>
        </nav>
        <div class="level">
            <a class="level-item button is-link is-rounded" href="https://github.com/duankong" target="_blank">
                Follow</a>
        </div>
        
        
        <div class="level is-mobile">
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Github" href="https://github.com/duankong">
                
                <i class="fab fa-github"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Facebook" href="https://facebook.com">
                
                <i class="fab fa-facebook"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Twitter" href="https://twitter.com">
                
                <i class="fab fa-twitter"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="Dribbble" href="https://dribbble.com">
                
                <i class="fab fa-dribbble"></i>
                
            </a>
            
            <a class="level-item button is-white is-marginless" target="_blank" title="RSS" href="/">
                
                <i class="fas fa-rss"></i>
                
            </a>
            
        </div>
        
    </div>
</div>
    
        
<div class="card widget" id="toc">
    <div class="card-content">
        <div class="menu">
            <h3 class="menu-label">
                Catalogue
            </h3>
            <ul class="menu-list"><li>
        <a class="is-flex" href="#🤹‍-小技巧">
        <span class="has-mr-6">1</span>
        <span>🤹‍ 小技巧</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🚵-两个指针">
        <span class="has-mr-6">1.1</span>
        <span>🚵 两个指针</span>
        </a></li><li>
        <a class="is-flex" href="#🤸‍-递归时传递多个参数-typedef-pair-lt-int-int-gt-P">
        <span class="has-mr-6">1.2</span>
        <span>🤸‍ 递归时传递多个参数  typedef pair&lt;int, int&gt; P;</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#🏊‍-算法">
        <span class="has-mr-6">2</span>
        <span>🏊‍ 算法</span>
        </a></li><li>
        <a class="is-flex" href="#🥘-二叉平衡树（Balanced-Binary-Tree）">
        <span class="has-mr-6">3</span>
        <span>🥘 二叉平衡树（Balanced Binary Tree）</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🍦-定义">
        <span class="has-mr-6">3.1</span>
        <span>🍦 定义</span>
        </a></li><li>
        <a class="is-flex" href="#🍯-C-实现建立树">
        <span class="has-mr-6">3.2</span>
        <span>🍯 C++实现建立树</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#🍵-完全二叉树（complete-binary-tree）">
        <span class="has-mr-6">4</span>
        <span>🍵 完全二叉树（complete binary tree）</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🥂-定义">
        <span class="has-mr-6">4.1</span>
        <span>🥂 定义</span>
        </a></li><li>
        <a class="is-flex" href="#🏺-判断（C-实现）">
        <span class="has-mr-6">4.2</span>
        <span>🏺 判断（C++实现）</span>
        </a></li><li>
        <a class="is-flex" href="#🏄-LCS-最长公共子序列">
        <span class="has-mr-6">4.3</span>
        <span>🏄 LCS 最长公共子序列</span>
        </a></li><li>
        <a class="is-flex" href="#🛀-堆排序-1098-Insertion-or-Heap-Sort-25">
        <span class="has-mr-6">4.4</span>
        <span>🛀 堆排序 1098 Insertion or Heap Sort (25)</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#👭-实现">
        <span class="has-mr-6">4.4.1</span>
        <span>👭 实现</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#💑-树状数组">
        <span class="has-mr-6">4.5</span>
        <span>💑 树状数组</span>
        </a></li><li>
        <a class="is-flex" href="#👩‍👩‍👧-单源最短路径-迪杰斯特拉算法">
        <span class="has-mr-6">4.6</span>
        <span>👩‍👩‍👧 单源最短路径 迪杰斯特拉算法</span>
        </a></li><li>
        <a class="is-flex" href="#👥-拓扑排序-1146-Topological-Order-25-分">
        <span class="has-mr-6">4.7</span>
        <span>👥 拓扑排序 1146 Topological Order (25 分)</span>
        </a></li><li>
        <a class="is-flex" href="#🦄-红黑树-1135-Is-It-A-Red-Black-Tree-30-分">
        <span class="has-mr-6">4.8</span>
        <span>🦄 红黑树 1135 Is It A Red-Black Tree (30 分)</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🦏-定义">
        <span class="has-mr-6">4.8.1</span>
        <span>🦏 定义</span>
        </a></li><li>
        <a class="is-flex" href="#🕊-规则4C-判断">
        <span class="has-mr-6">4.8.2</span>
        <span>🕊 规则4C++判断</span>
        </a></li><li>
        <a class="is-flex" href="#🐠-规则5C-判断">
        <span class="has-mr-6">4.8.3</span>
        <span>🐠 规则5C++判断</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#🦂-Hashing-插入和查找-1078-Hashing-25-分-1145-Hashing-Average-Search-Time-25-分">
        <span class="has-mr-6">4.9</span>
        <span>🦂 Hashing 插入和查找: 1078 Hashing (25 分) 1145 Hashing - Average Search Time (25 分)</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🌺-插入">
        <span class="has-mr-6">4.9.1</span>
        <span>🌺 插入</span>
        </a></li><li>
        <a class="is-flex" href="#🌻-查找">
        <span class="has-mr-6">4.9.2</span>
        <span>🌻 查找</span>
        </a></li></ul></li><li>
        <a class="is-flex" href="#🍂-背包问题">
        <span class="has-mr-6">4.10</span>
        <span>🍂 背包问题</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#🍇-通用解法">
        <span class="has-mr-6">4.10.1</span>
        <span>🍇 通用解法</span>
        </a></li><li>
        <a class="is-flex" href="#🍑-一维">
        <span class="has-mr-6">4.10.2</span>
        <span>🍑 一维</span>
        </a></li></ul></li></ul></li></ul>
        </div>
    </div>
</div>

    
        
<div class="card widget">
    <div class="card-content">
        <div class="menu">
            <h3 class="menu-label">
                Categories
            </h3>
            <ul class="menu-list">
            <li>
        <a class="level is-marginless" href="/categories/C/">
            <span class="level-start">
                <span class="level-item">C++</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">9</span>
            </span>
        </a><ul><li>
        <a class="level is-marginless" href="/categories/C/Algorithm/">
            <span class="level-start">
                <span class="level-item">Algorithm</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">2</span>
            </span>
        </a></li><li>
        <a class="level is-marginless" href="/categories/C/Basic-knowledge/">
            <span class="level-start">
                <span class="level-item">Basic knowledge</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">4</span>
            </span>
        </a></li><li>
        <a class="level is-marginless" href="/categories/C/PAT-Note/">
            <span class="level-start">
                <span class="level-item">PAT Note</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">3</span>
            </span>
        </a></li></ul></li><li>
        <a class="level is-marginless" href="/categories/Learning/">
            <span class="level-start">
                <span class="level-item">Learning</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">3</span>
            </span>
        </a><ul><li>
        <a class="level is-marginless" href="/categories/Learning/Dimensionality-Reduction/">
            <span class="level-start">
                <span class="level-item">Dimensionality-Reduction</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">1</span>
            </span>
        </a></li><li>
        <a class="level is-marginless" href="/categories/Learning/Feature-Extraction/">
            <span class="level-start">
                <span class="level-item">Feature-Extraction</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">1</span>
            </span>
        </a></li><li>
        <a class="level is-marginless" href="/categories/Learning/Matlab/">
            <span class="level-start">
                <span class="level-item">Matlab</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">1</span>
            </span>
        </a></li></ul></li><li>
        <a class="level is-marginless" href="/categories/Learning-Note/">
            <span class="level-start">
                <span class="level-item">Learning Note</span>
            </span>
            <span class="level-end">
                <span class="level-item tag">2</span>
            </span>
        </a></li>
            </ul>
        </div>
    </div>
</div>
    
        

<div class="card widget">
    <div class="card-content">
        <div class="menu">
        <h3 class="menu-label">
            Links
        </h3>
        <ul class="menu-list">
        
            <li>
                <a class="level is-mobile" href="https://github.com/duankong" target="_blank">
                    <span class="level-left">
                        <span class="level-item">Github</span>
                    </span>
                    <span class="level-right">
                        <span class="level-item tag">github.com</span>
                    </span>
                </a>
            </li>
        
            <li>
                <a class="level is-mobile" href="https://google.com" target="_blank">
                    <span class="level-left">
                        <span class="level-item">Google</span>
                    </span>
                    <span class="level-right">
                        <span class="level-item tag">google.com</span>
                    </span>
                </a>
            </li>
        
            <li>
                <a class="level is-mobile" href="https://baidu.com" target="_blank">
                    <span class="level-left">
                        <span class="level-item">Baidu</span>
                    </span>
                    <span class="level-right">
                        <span class="level-item tag">baidu.com</span>
                    </span>
                </a>
            </li>
        
        </ul>
        </div>
    </div>
</div>


    
        
<div class="card widget">
    <div class="card-content">
        <h3 class="menu-label">
            Tag Cloud
        </h3>
        <a href="/tags/01背包问题/" style="font-size: 10px;">01背包问题</a> <a href="/tags/BST/" style="font-size: 10px;">BST</a> <a href="/tags/Bigtiff/" style="font-size: 10px;">Bigtiff</a> <a href="/tags/C/" style="font-size: 20px;">C++</a> <a href="/tags/Dijkstra/" style="font-size: 10px;">Dijkstra</a> <a href="/tags/Function/" style="font-size: 10px;">Function</a> <a href="/tags/KKT/" style="font-size: 10px;">KKT</a> <a href="/tags/LCS/" style="font-size: 10px;">LCS</a> <a href="/tags/Matlab/" style="font-size: 10px;">Matlab</a> <a href="/tags/PAT/" style="font-size: 10px;">PAT</a> <a href="/tags/PCA降维/" style="font-size: 10px;">PCA降维</a> <a href="/tags/Queue/" style="font-size: 10px;">Queue</a> <a href="/tags/String/" style="font-size: 10px;">String</a> <a href="/tags/hashing/" style="font-size: 10px;">hashing</a> <a href="/tags/hashing查找/" style="font-size: 10px;">hashing查找</a> <a href="/tags/三维图像/" style="font-size: 10px;">三维图像</a> <a href="/tags/中序遍历/" style="font-size: 10px;">中序遍历</a> <a href="/tags/二叉平衡树/" style="font-size: 10px;">二叉平衡树</a> <a href="/tags/二叉搜索树/" style="font-size: 10px;">二叉搜索树</a> <a href="/tags/二阶偏导数/" style="font-size: 10px;">二阶偏导数</a> <a href="/tags/先序遍历/" style="font-size: 10px;">先序遍历</a> <a href="/tags/凸函数，正交和投影/" style="font-size: 10px;">凸函数，正交和投影</a> <a href="/tags/动态规划/" style="font-size: 15px;">动态规划</a> <a href="/tags/变量类型/" style="font-size: 10px;">变量类型</a> <a href="/tags/后序遍历/" style="font-size: 10px;">后序遍历</a> <a href="/tags/堆排序/" style="font-size: 15px;">堆排序</a> <a href="/tags/字符串/" style="font-size: 10px;">字符串</a> <a href="/tags/完全二叉树/" style="font-size: 10px;">完全二叉树</a> <a href="/tags/容器/" style="font-size: 10px;">容器</a> <a href="/tags/常量/" style="font-size: 10px;">常量</a> <a href="/tags/并查集/" style="font-size: 10px;">并查集</a> <a href="/tags/广度-层次-遍历/" style="font-size: 10px;">广度(层次)遍历</a> <a href="/tags/归并排序/" style="font-size: 10px;">归并排序</a> <a href="/tags/拉格朗日乘子/" style="font-size: 10px;">拉格朗日乘子</a> <a href="/tags/拓扑排序/" style="font-size: 15px;">拓扑排序</a> <a href="/tags/指针/" style="font-size: 10px;">指针</a> <a href="/tags/插入排序/" style="font-size: 10px;">插入排序</a> <a href="/tags/文件读写/" style="font-size: 10px;">文件读写</a> <a href="/tags/无偏估计/" style="font-size: 10px;">无偏估计</a> <a href="/tags/朴素贝叶斯算法/" style="font-size: 10px;">朴素贝叶斯算法</a> <a href="/tags/树状数组/" style="font-size: 15px;">树状数组</a> <a href="/tags/梯度散度和旋度/" style="font-size: 10px;">梯度散度和旋度</a> <a href="/tags/海森矩阵/" style="font-size: 10px;">海森矩阵</a> <a href="/tags/深度遍历/" style="font-size: 10px;">深度遍历</a> <a href="/tags/病毒标记/" style="font-size: 10px;">病毒标记</a> <a href="/tags/算法/" style="font-size: 15px;">算法</a> <a href="/tags/红黑树/" style="font-size: 15px;">红黑树</a> <a href="/tags/背包问题/" style="font-size: 10px;">背包问题</a> <a href="/tags/迪杰斯特拉算法，最短路径/" style="font-size: 10px;">迪杰斯特拉算法，最短路径</a> <a href="/tags/高斯函数/" style="font-size: 10px;">高斯函数</a>
    </div>
</div>

    
    
        <div class="column-right-shadow is-hidden-widescreen is-sticky">
        
            
<div class="card widget">
    <div class="card-content">
        <h3 class="menu-label">
            Recent
        </h3>
        
        <article class="media">
            
            <a href="/2019/12/09/Function-for-Check/" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="https://images.pexels.com/photos/2994325/pexels-photo-2994325.jpeg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="Function for Check">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-12-09T10:24:41.000Z">2019-12-09</time></div>
                    <a href="/2019/12/09/Function-for-Check/" class="has-link-black-ter is-size-6">Function for Check</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/C/">C++</a> / <a class="has-link-grey -link" href="/categories/C/Basic-knowledge/">Basic knowledge</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/2019/12/08/PAT-小结/" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="https://images.pexels.com/photos/3290601/pexels-photo-3290601.jpeg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="PAT 小结">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-12-08T10:09:29.000Z">2019-12-08</time></div>
                    <a href="/2019/12/08/PAT-小结/" class="has-link-black-ter is-size-6">PAT 小结</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/C/">C++</a> / <a class="has-link-grey -link" href="/categories/C/PAT-Note/">PAT Note</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/2019/12/08/PAT-Note-2/" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="https://images.pexels.com/photos/3210189/pexels-photo-3210189.jpeg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="PAT Note 2">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-12-08T09:46:17.000Z">2019-12-08</time></div>
                    <a href="/2019/12/08/PAT-Note-2/" class="has-link-black-ter is-size-6">PAT Note 2</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/C/">C++</a> / <a class="has-link-grey -link" href="/categories/C/PAT-Note/">PAT Note</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/2019/12/03/PAT-note-1/" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="https://images.pexels.com/photos/33109/fall-autumn-red-season.jpg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="PAT note 1">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-12-03T14:32:21.000Z">2019-12-03</time></div>
                    <a href="/2019/12/03/PAT-note-1/" class="has-link-black-ter is-size-6">PAT note 1</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/C/">C++</a> / <a class="has-link-grey -link" href="/categories/C/PAT-Note/">PAT Note</a>
                    </p>
                </div>
            </div>
        </article>
        
        <article class="media">
            
            <a href="/2019/12/02/背包问题/" class="media-left">
                <p class="image is-64x64">
                    <img class="thumbnail" src="https://images.pexels.com/photos/2931242/pexels-photo-2931242.jpeg?auto=compress&amp;cs=tinysrgb&amp;dpr=1&amp;w=500" alt="背包问题">
                </p>
            </a>
            
            <div class="media-content">
                <div class="content">
                    <div><time class="has-text-grey is-size-7 is-uppercase" datetime="2019-12-02T15:39:41.000Z">2019-12-02</time></div>
                    <a href="/2019/12/02/背包问题/" class="has-link-black-ter is-size-6">背包问题</a>
                    <p class="is-size-7 is-uppercase">
                        <a class="has-link-grey -link" href="/categories/C/">C++</a> / <a class="has-link-grey -link" href="/categories/C/Algorithm/">Algorithm</a>
                    </p>
                </div>
            </div>
        </article>
        
    </div>
</div>

        
            <div class="card widget">
    <div class="card-content">
        <div class="menu">
        <h3 class="menu-label">
            Archives
        </h3>
        <ul class="menu-list">
        
        <li>
            <a class="level is-marginless" href="/archives/2019/12/">
                <span class="level-start">
                    <span class="level-item">December 2019</span>
                </span>
                <span class="level-end">
                    <span class="level-item tag">5</span>
                </span>
            </a>
        </li>
        
        <li>
            <a class="level is-marginless" href="/archives/2019/11/">
                <span class="level-start">
                    <span class="level-item">November 2019</span>
                </span>
                <span class="level-end">
                    <span class="level-item tag">1</span>
                </span>
            </a>
        </li>
        
        <li>
            <a class="level is-marginless" href="/archives/2019/10/">
                <span class="level-start">
                    <span class="level-item">October 2019</span>
                </span>
                <span class="level-end">
                    <span class="level-item tag">4</span>
                </span>
            </a>
        </li>
        
        <li>
            <a class="level is-marginless" href="/archives/2018/11/">
                <span class="level-start">
                    <span class="level-item">November 2018</span>
                </span>
                <span class="level-end">
                    <span class="level-item tag">3</span>
                </span>
            </a>
        </li>
        
        <li>
            <a class="level is-marginless" href="/archives/2018/10/">
                <span class="level-start">
                    <span class="level-item">October 2018</span>
                </span>
                <span class="level-end">
                    <span class="level-item tag">1</span>
                </span>
            </a>
        </li>
        
        </ul>
        </div>
    </div>
</div>
        
            <div class="card widget">
    <div class="card-content">
        <div class="menu">
            <h3 class="menu-label">
                Tags
            </h3>
            <div class="field is-grouped is-grouped-multiline">
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/01背包问题/">
                        <span class="tag">01背包问题</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/BST/">
                        <span class="tag">BST</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/Bigtiff/">
                        <span class="tag">Bigtiff</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/C/">
                        <span class="tag">C++</span>
                        <span class="tag is-grey">9</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/Dijkstra/">
                        <span class="tag">Dijkstra</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/Function/">
                        <span class="tag">Function</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/KKT/">
                        <span class="tag">KKT</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/LCS/">
                        <span class="tag">LCS</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/Matlab/">
                        <span class="tag">Matlab</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/PAT/">
                        <span class="tag">PAT</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/PCA降维/">
                        <span class="tag">PCA降维</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/Queue/">
                        <span class="tag">Queue</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/String/">
                        <span class="tag">String</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/hashing/">
                        <span class="tag">hashing</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/hashing查找/">
                        <span class="tag">hashing查找</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/三维图像/">
                        <span class="tag">三维图像</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/中序遍历/">
                        <span class="tag">中序遍历</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/二叉平衡树/">
                        <span class="tag">二叉平衡树</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/二叉搜索树/">
                        <span class="tag">二叉搜索树</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/二阶偏导数/">
                        <span class="tag">二阶偏导数</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/先序遍历/">
                        <span class="tag">先序遍历</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/凸函数，正交和投影/">
                        <span class="tag">凸函数，正交和投影</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/动态规划/">
                        <span class="tag">动态规划</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/变量类型/">
                        <span class="tag">变量类型</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/后序遍历/">
                        <span class="tag">后序遍历</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/堆排序/">
                        <span class="tag">堆排序</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/字符串/">
                        <span class="tag">字符串</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/完全二叉树/">
                        <span class="tag">完全二叉树</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/容器/">
                        <span class="tag">容器</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/常量/">
                        <span class="tag">常量</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/并查集/">
                        <span class="tag">并查集</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/广度-层次-遍历/">
                        <span class="tag">广度(层次)遍历</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/归并排序/">
                        <span class="tag">归并排序</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/拉格朗日乘子/">
                        <span class="tag">拉格朗日乘子</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/拓扑排序/">
                        <span class="tag">拓扑排序</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/指针/">
                        <span class="tag">指针</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/插入排序/">
                        <span class="tag">插入排序</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/文件读写/">
                        <span class="tag">文件读写</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/无偏估计/">
                        <span class="tag">无偏估计</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/朴素贝叶斯算法/">
                        <span class="tag">朴素贝叶斯算法</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/树状数组/">
                        <span class="tag">树状数组</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/梯度散度和旋度/">
                        <span class="tag">梯度散度和旋度</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/海森矩阵/">
                        <span class="tag">海森矩阵</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/深度遍历/">
                        <span class="tag">深度遍历</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/病毒标记/">
                        <span class="tag">病毒标记</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/算法/">
                        <span class="tag">算法</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/红黑树/">
                        <span class="tag">红黑树</span>
                        <span class="tag is-grey">2</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/背包问题/">
                        <span class="tag">背包问题</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/迪杰斯特拉算法，最短路径/">
                        <span class="tag">迪杰斯特拉算法，最短路径</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
                <div class="control">
                    <a class="tags has-addons" href="/tags/高斯函数/">
                        <span class="tag">高斯函数</span>
                        <span class="tag is-grey">1</span>
                    </a>
                </div>
                
            </div>
        </div>
    </div>
</div>
        
        </div>
    
</div>

                

<!-- 粘贴的部分 -->

            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
				<script src="//code.tidio.co/3tnny2tdx9oh0xzuitaxzhuakj60ydfy.js"></script>
                <a class="footer-logo is-block has-mb-12" href="/">
                
                    <img src="/images/dk_logo.svg" alt="PAT 小结" width="304" height="50">
                
                </a>
                <p class="is-size-10">
                &copy; 2019 duankong&nbsp;
                Powered by <a href="https://hexo.io/" target="_blank">Hexo</a> & <a href="https://github.com/ppoffice/hexo-theme-icarus" target="_blank">Icarus</a>
                
                <br>
                <span id="busuanzi_container_site_uv">
                &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
                <i class="fa fa-bolt" aria-hidden="true "></i>
                Visited by <span id="busuanzi_value_site_uv">0</span> users
                <i class="fa fa-bolt" aria-hidden="true "></i>
                </span>
                
                </p>
            </div>
            
            <span id="timeDate">载入天数...</span><span id="times">载入时分秒...</span>
            <script>
                var now = new Date(); 
                function createtime() { 
                    var grt= new Date("5/25/2019 11:50:00");//此处修改你的建站时间或者网站上线时间 
                    now.setTime(now.getTime()+250); 
                    days = (now - grt ) / 1000 / 60 / 60 / 24; dnum = Math.floor(days); 
                    hours = (now - grt ) / 1000 / 60 / 60 - (24 * dnum); hnum = Math.floor(hours); 
                    if(String(hnum).length ==1 ){hnum = "0" + hnum;} minutes = (now - grt ) / 1000 /60 - (24 * 60 * dnum) - (60 * hnum); 
                    mnum = Math.floor(minutes); if(String(mnum).length ==1 ){mnum = "0" + mnum;} 
                    seconds = (now - grt ) / 1000 - (24 * 60 * 60 * dnum) - (60 * 60 * hnum) - (60 * mnum); 
                    snum = Math.round(seconds); if(String(snum).length ==1 ){snum = "0" + snum;} 
                    document.getElementById("timeDate").innerHTML = "Security Run For "+dnum+" Day "; 
                    document.getElementById("times").innerHTML = hnum + " Hour " + mnum + " Min " + snum + " Second"; 
                } 
            setInterval("createtime()",250);
            </script>
            
            <div class="level-end">
            
                <div class="field has-addons is-flex-center-mobile has-mt-5-mobile is-flex-wrap is-flex-middle">
                
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" title="Creative Commons" href="https://creativecommons.org/">
                        
                        <i class="fab fa-creative-commons"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" title="Attribution 4.0 International" href="https://creativecommons.org/licenses/by/4.0/">
                        
                        <i class="fab fa-creative-commons-by"></i>
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" title="Download on GitHub" href="https://github.com/duankong">
                        
                        <i class="fab fa-github"></i>
                        
                    </a>
                </p>
                
                </div>
            
            </div>
        </div>
    </div>

	
</footer>
    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("en");</script>


    
    
    
    <script src="/js/animation.js"></script>
    

    
    
    
    <script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
    <script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
    <script src="/js/gallery.js" defer></script>
    

    
    

<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


    
    
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>

    
    

<a id="back-to-top" title="Back to Top" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>


    
    

    
    
    
    

    
    
    
    
    
    <script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>
    <script src="/js/clipboard.js" defer></script>
    

    
    
    

    


<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="Type something...">
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: 'Posts',
                PAGES: 'Pages',
                CATEGORIES: 'Categories',
                TAGS: 'Tags',
                UNTITLED: '(Untitled)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
    

	
	<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"debug":false,"model":{"jsonPath":"/live2dw/assets/koharu.model.json"},"display":{"position":"left","width":150,"height":300},"mobile":{"show":true},"log":false});</script></body>

</html>